class Task3Copy:
    def run(self, array):
        array = [e for e in array]
        for i in range(len(array)):
            while i != array[i]:
                if array[i] == array[array[i]]:
                    return array[i]
                temp = array[i]
                array[i] = array[temp]
                array[temp] = temp
        return None


class Task3Inplace:
    def run(self, array):
        start = 0
        end = len(array)
        middle = (start + end) // 2
        while middle > start or end > middle:
            count = self.count_number_in_range(array, start, middle)
            if count > middle - start:
                if middle - start == 1:
                    return start
                end = middle
                middle = (start + end) // 2
            else:
                count = self.count_number_in_range(array, middle, end)
                if count > end - middle:
                    if end - middle == 1:
                        return middle
                    start = middle
                    middle = (start + end) // 2
                else:
                    return None
        return None

    def count_number_in_range(self, array, start, end):
        # start: inclusive
        # end: exclusive
        count = 0
        for num in array:
            if start <= num < end:
                count += 1
        return count
